/**
 * 
 */
package cn.edu.cqu.bysj.wm.ago.gn;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import org.neo4j.graphalgo.CommonEvaluators;
import org.neo4j.graphalgo.CostEvaluator;
import org.neo4j.graphalgo.GraphAlgoFactory;
import org.neo4j.graphalgo.PathFinder;
import org.neo4j.graphalgo.WeightedPath;
import org.neo4j.graphalgo.impl.shortestpath.SingleSourceShortestPath;
import org.neo4j.graphalgo.impl.shortestpath.SingleSourceShortestPathBFS;
import org.neo4j.graphdb.Direction;
import org.neo4j.graphdb.GraphDatabaseService;
import org.neo4j.graphdb.Node;
import org.neo4j.graphdb.Relationship;
import org.neo4j.graphdb.RelationshipExpander;
import org.neo4j.graphdb.Transaction;
import org.neo4j.kernel.Traversal;
import org.ujmp.core.Matrix;

import cn.edu.cqu.bysj.wm.def.ConstDef;
import cn.edu.cqu.bysj.wm.def.PropertyDef;
import cn.edu.cqu.bysj.wm.def.RelTypeDef;
import cn.edu.cqu.bysj.wm.def.Weight;
import cn.edu.cqu.bysj.wm.util.CalcTime;
import cn.edu.cqu.bysj.wm.util.ImportData;

/**
 * @author Meng
 * 
 */
public class GN {

	public List<Node> nodes = new ArrayList<Node>();
	public GraphDatabaseService gdb;
	public HierarchyTree tree = new HierarchyTree();
	public Matrix matrix;
	public String path;
	public Weight weight;
	public int n, e = 0;

	// betweenness value of each edge
	public HashMap<Long, Integer> betweenness = new HashMap<Long, Integer>();

	public long leftEdge, initTime, iterTime, bTime = 0;

	/**
	 * @param path
	 * @param gdb
	 * @param tdb
	 * @param type
	 */
	public GN(String path, GraphDatabaseService gdb, GraphDatabaseService tdb,
			Weight type) {
		long t = System.currentTimeMillis();

		this.path = path;
		this.gdb = gdb;
		this.weight = type;

		addData();

		tree.initTree(nodes, tdb);
		initTime = CalcTime.calcRunTime(t);
	}

	/**
	 * GN iteration process
	 */
	public void IterationGN() {

		long t = System.currentTimeMillis();

		Set<Long> rids = betweenness.keySet();

		// calc betweenness of all relationship
		calcBetweenness(rids);

		// still has edge left
		while (leftEdge > 0) {

			// find the edge and value which value is max in betweenness
			long key = maxBetweennessEdge(rids);
			int value = betweenness.get(key);

			// judge n-1 rule
			if (JudgeRule.judgeNSub1Rule(value, n - 1) == 0) {
				System.out.println("break n-1 rule, GN quit");
				break;
			}

			Relationship relationship = gdb.getRelationshipById(key);
			Node sNode = relationship.getStartNode();
			Node eNode = relationship.getEndNode();

			long eid = deleteEdge(relationship, sNode, eNode);

			// judge partition then judge minimum component rule
			// according to the result flag it return, choose the way to
			// calculate betweenness

			long t1 = 0;
			int flag = JudgeRule.judgePartition(sNode, eNode, gdb, tree);

			if (flag == ConstDef.LESS_THAN_TTREE) {

				lockEdge(sNode, eNode, eid);

			} else if (flag == ConstDef.PARTITION_OK) {
				// recalculate betweenness in two seperate component

				t1 = System.currentTimeMillis();

				// component from the start node
				Set<Relationship> srSet = new HashSet<Relationship>(
						JudgeRule.srList);
				Set<Node> snSet = new HashSet<Node>(JudgeRule.snList);

				if (weight.equals(Weight.WEIGHTED)) {
					calcBetweennessDijsktra(srSet, snSet);
				} else {
					calcBetweennessBFS(srSet, snSet);
				}
				
				// component from the end node
				Set<Relationship> erSet = new HashSet<Relationship>(
						JudgeRule.erList);
				Set<Node> enSet = new HashSet<Node>(JudgeRule.enList);

				if (weight.equals(Weight.WEIGHTED)) {
					calcBetweennessDijsktra(erSet, enSet);
				} else {
					calcBetweennessBFS(erSet, enSet);
				}
				
				bTime += CalcTime.calcRunTime(t1);
			} else if (flag == ConstDef.ONLY_DELETE_EDGE) {
				// recalculate betweenness, still this whole component

				t1 = System.currentTimeMillis();

				if (weight.equals(Weight.WEIGHTED)) {
					calcBetweennessDijsktra(JudgeRule.componentRels,
							JudgeRule.componentNodes);
				} else {
					calcBetweennessBFS(JudgeRule.componentRels,
							JudgeRule.componentNodes);
				}
				bTime += CalcTime.calcRunTime(t1);
			}
		}
		iterTime = CalcTime.calcRunTime(t);

	}

	/**
	 * use BFS to calculate betweenness in unweighted and undirected graph
	 * 
	 * @param rels
	 * @param nodes
	 */
	private void calcBetweennessBFS(Set<Relationship> rels, Set<Node> nodes) {

		// clear betweenness
		for (Relationship rel : rels) {
			betweenness.put(rel.getId(), 0);
		}

		for (Node node1 : nodes) {
			// prepare arguments for BFS in neo4j
			SingleSourceShortestPath<Integer> ssspBFS = new SingleSourceShortestPathBFS(
					node1, Direction.BOTH, RelTypeDef.EDGE, RelTypeDef.LOCK);

			for (Node node2 : nodes) {

				if (node1.getId() != node2.getId()) {

					// single source shortest path BFS returns the relationships
					// of a shortest path
					for (Relationship rel : ssspBFS
							.getPathAsRelationships(node2)) {

						// update betweenness of edge if the edge is not
						// locked
						if (!rel.getType().equals(RelTypeDef.LOCK)) {
							long key = rel.getId();
							betweenness.put(key, betweenness.get(key) + 1);
						}
					}
				}
			}
		}
	}

	/**
	 * use Dijsktra to calculate betweenness in unweighted and undirected graph
	 * improve of calculate betweenness
	 * 
	 * @param rels
	 * @param nodes
	 */
	private void calcBetweennessDijsktra(Set<Relationship> rels, Set<Node> nodes) {

		// clear betweenness
		for (Relationship rel : rels) {
			betweenness.put(rel.getId(), 0);
		}

		// prepare arguments for Dijsktra in neo4j
		RelationshipExpander expander = Traversal.expanderForTypes(
				RelTypeDef.EDGE, Direction.BOTH).add(RelTypeDef.LOCK);
		CostEvaluator<Double> costEvaluator = CommonEvaluators
				.doubleCostEvaluator(PropertyDef.WEIGHT);

		// shortest path finder
		PathFinder<WeightedPath> pFinder = GraphAlgoFactory.dijkstra(expander,
				costEvaluator);

		// calculate betweenness of each pair of nodes
		for (Node node1 : nodes) {
			for (Node node2 : nodes) {
				if (node1.getId() != node2.getId()) {

					// single shortest path from node 1 to 2 ,path must exists
					WeightedPath wPath = pFinder.findSinglePath(node1, node2);

					for (Relationship rel : wPath.relationships()) {
						// update betweenness of edge if the edge is not
						// locked
						if (!rel.getType().equals(RelTypeDef.LOCK)) {
							long key = rel.getId();
							betweenness.put(key, betweenness.get(key) + 1);
						}
					}
				}
			}
		}
	}

	/**
	 * old method to calculate betweenness and each time update betweenness of
	 * all existing relationships
	 * 
	 * @param rids
	 */
	private void calcBetweenness(Set<Long> rids) {

		// clear betweenness
		for (long id : rids) {
			betweenness.put(id, 0);
		}

		// prepare arguments for dijsktra in neo4j
		RelationshipExpander expander = Traversal.expanderForTypes(
				RelTypeDef.EDGE, Direction.BOTH).add(RelTypeDef.LOCK);
		CostEvaluator<Double> costEvaluator = CommonEvaluators
				.doubleCostEvaluator(PropertyDef.WEIGHT);

		// shortest path finder
		PathFinder<WeightedPath> pFinder = GraphAlgoFactory.dijkstra(expander,
				costEvaluator);

		// betweenness calculated in relationships of all pair of nodes(i and j)
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++) {

				// single shortest path from node i to j
				WeightedPath wPath = pFinder.findSinglePath(gdb.getNodeById(i),
						gdb.getNodeById(j));

				// node i and j may be disconnected
				if (wPath != null) {
					for (Relationship rel : wPath.relationships()) {

						// update betweenness if edge can be calculated
						if (!rel.getType().equals(RelTypeDef.LOCK)) {
							long key = rel.getId();
							betweenness.put(key, betweenness.get(key) + 1);
						}
					}
				}
			}
		}
	}

	/**
	 * find max betweenness edge
	 * 
	 * @param edges
	 * @return max betweenness value
	 */
	private long maxBetweennessEdge(Set<Long> edges) {
		int maxValue = Collections.max(betweenness.values());
		for (long key : edges) {
			if (betweenness.get(key) == maxValue)
				return key;
		}
		return -1;
	}

	/**
	 * lock an edge ,so we will not calculate the betweenness of it
	 * 
	 * @param sNode
	 *            start node
	 * @param eNode
	 *            end node
	 * @param eid
	 *            relationship id
	 */
	private void lockEdge(Node sNode, Node eNode, long eid) {
		Relationship del = gdb.getRelationshipById(eid);
		Transaction tx = gdb.beginTx();
		try {
			// create a new relationship type is lock
			sNode.createRelationshipTo(eNode, RelTypeDef.LOCK).setProperty(
					PropertyDef.WEIGHT, del.getProperty(PropertyDef.WEIGHT));
			del.delete();
			tx.success();
		} finally {
			tx.finish();
		}
	}

	/**
	 * delete an edge, actually create a new relationship which type is delete
	 * 
	 * @param rel
	 *            relationship to delete
	 * @param sNode
	 *            start node
	 * @param eNode
	 *            end node
	 * @return new delete edge id
	 */
	private long deleteEdge(Relationship rel, Node sNode, Node eNode) {

		Transaction tx = gdb.beginTx();
		long id = rel.getId();
		Relationship del;
		try {
			// create a new relationship type is delete
			del = sNode.createRelationshipTo(eNode, RelTypeDef.DELETE);
			del.setProperty(PropertyDef.WEIGHT,
					rel.getProperty(PropertyDef.WEIGHT));
			// delete the old edge
			rel.delete();
			tx.success();
		} finally {
			tx.finish();
			betweenness.remove(id);
			leftEdge--;
		}
		return del.getId();
	}

	/**
	 * add data to neo4j graph database
	 */
	private void addData() {

		// import data from file path
		matrix = ImportData.importData(path, weight);
		n = ImportData.n;

		Transaction tx = gdb.beginTx();
		try {
			// initial nodes
			for (int i = 0; i < n; i++) { // initial sequence of nodes
				Node node = gdb.createNode();
				node.setProperty(PropertyDef.SEQUENCE, i + 1);
				node.setProperty(PropertyDef.COMMUNITY_ID, 1L);
				nodes.add(node);
			}

			// initial relationships of nodes
			for (int i = 0; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					int weight = matrix.getAsInt(i, j);
					if (weight >= 1) {
						e++;
						// int weight = (int) (Math.random() * 10+1);

						Relationship rel = nodes.get(i).createRelationshipTo(
								nodes.get(j), RelTypeDef.EDGE);
						rel.setProperty(PropertyDef.WEIGHT, weight);
						betweenness.put(rel.getId(), 0);
					}
				}
			}
			tx.success();
		} finally {
			tx.finish();
		}
		leftEdge = e;
	}

}
